COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00015 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A64.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 5, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Nondeterministic Machines\hfill}

Nondeterministic programs (NDP) for any machine are defined much as
deterministic programs, except that multiple choices may be provided
at certain points in a computation. There is a set~$S$ of initial
control states; in a deterministic program, $|S|=1$. A~program is a
set of instructions; in a deterministic program, the instructions have
disjoint domains. Viewing a program as a relation between consecutive
configurations, a~deterministic program is a partial function, while
a non-deterministic program is a relation that may map a configuration
into more than one sequel.

The input-output relation of an NDP is still $\alpha\pi↑{\ast}\omega$,
where $\alpha$ is a relation (not always a function) mapping argument
to initial configuration, $\pi$~is a program, and $\omega$ a relation
from final configuration to result.

\medskip\noindent
{\bf Example:} A nondeterministic program $\pi$ for a one-stack machine 
with devices $\langle$control, input, right stack$\rangle$
accepts strings of even length that, like $abbabbabba$, are equal
to their own reflections; $x=u\hat{u}$ for some $u\in\{a,b\}↑{\ast}$.

\bigskip
$$\vcenter{\offinterlineskip%
\halign{%
$\hfil#\hfil$\quad&$\hfil#\hfil$\quad&#\hfil\qquad\qquad%
&$\hfil#\hfil$\quad&#\hfil\quad&#\hfil\qquad%
&$\hfil#\hfil$\quad&$\hfil#\hfil$\cr
&&{\tt SCAN} $a$ {\tt PUSH} $a$&&{\tt SCAN} $a$ {\tt POP} $a$\cr
\noalign{\bigskip\bigskip}
&&\hfill{\tt NOP}&&&{\tt EOF EMPTY}\cr
\Rightarrow&1&&2&&&3&\Rightarrow\cr
\noalign{\bigskip\bigskip}
&&{\tt SCAN} $b$ {\tt PUSH} $b$&&{\tt SCAN} $b$ {\tt POP} $b$\cr
}}$$

\bigskip
$$u\hat{u}\,\alpha\langle 1,u\hat{u},\Lambda\rangle\pi↑{\ast}\langle 1,\hat{u},
u\rangle\pi\langle 2,\hat{u},u\rangle\pi↑{\ast}\langle 2,\Lambda,\Lambda\rangle
\pi\langle 3,\Lambda,\Lambda\rangle\omega\Lambda\,.$$

\bigskip
A related deterministic program $\pi↓{\rm{chk}}$ accepts only the traces of
program~$\pi$.

\bigskip
$$\vcenter{\offinterlineskip%
\halign{%
$\hfil#\hfil$\quad&\hfil#\hfil\quad&#\hfil\quad%
&\hfil#\hfil\quad&#\hfil\quad&\hfil#\hfil\quad%
&\hfil#\hfil\quad&#\hfil\quad&\hfil#\hfil\quad%
&$\hfil#\hfil$\cr
&&&&{\tt SCAN} ``11 {\tt SCAN} $a$ {\tt PUSH} $a$''&&{\tt SCAN} ``22 {\tt SCAN}
$a$ {\tt POP} $a$''\cr
\noalign{\bigskip\bigskip}
&&&&\hfill{\tt PUSH} $a$&&\hfill{\tt POP} $a$\cr
\noalign{\bigskip\bigskip}
&&{\tt SCAN} ``1''&&{\tt SCAN} ``12 {\tt NOOP NOOP}''&&{\tt SCAN} ``{\tt EOF
EMPTY}''\cr
\Rightarrow&0&&1&&2&&3&$\Rightarrow$\cr
&&&&&&{\tt EMPTY}\cr
\noalign{\bigskip\bigskip}
&&&&{\tt SCAN} ``11 {\tt SCAN} $b$ {\tt PUSH} $b$''&&{\tt SCAN} ``22 {\tt SCAN}
$b$ {\tt POP} $b$''\cr
\noalign{\bigskip\bigskip}
&&&&\hfill {\tt PUSH} $b$&&\hfill{\tt POP} $b$\cr
}}$$

\vfill\eject

This program uses its control and stack exactly as $\pi$ does. Where $\pi$
accepts $abba$, though, $\pi↓{\rm chk}$~accepts

\medskip
\halign{\qquad\qquad #\hfil\quad&{\tt #}\hfil\qquad&{\tt #}\hfil\cr
1\cr
11&SCAN $a$&PUSH $a$\cr
11&SCAN $b$&PUSH $b$\cr
12&NOP&NOP\cr
22&SCAN $b$&POP $b$\cr
22&SCAN $a$&POP $a$\cr
23&EOF&EMPTY\cr
}

\medskip\noindent
which is the computation of $\pi$ that accepts $abba$. Because every
instruction of $\pi↓{\rm chk}$ includes a {\tt SCAN} of its own unique
input string, $\pi↓{\rm chk}$~is deterministic. An~easy induction shows
that $\pi↓{\rm chk}$, after reading a part of a computation of~$\pi$,
is in the same control and stack states that $\pi$ would be in; after reading
1~11 {\tt SCAN}~$a$ {\tt PUSH}~$b$, $\pi↓{\rm chk}$~is in control state~1
and stack state~$b$.

It is fairly obvious that for any machine and nondeterministic program~$\pi$,
there is a deterministic program $\pi↓{\rm chk}$ for a similar machine
that accepts computations of~$\pi$. The difference between the machines is that
all the input and output devices of the $\pi$~machine have been removed,
and replaced by a left-to-right input with a rather large alphabet.

Since $\pi↓{\rm chk}$ ``knows'' exactly what $\pi$ is doing at all times,
it is easy to add outputs on which it records everything $\pi$ reads
or writes:

\bigskip
$$\vcenter{\offinterlineskip%
\halign{%
$\hfil#\hfil$\qquad&\hfil#\hfil\qquad&#\hfil\qquad\qquad
&\hfil#\hfil\qquad&#\hfil\qquad&\hfil#\hfil\qquad&#\hfil\cr
&&&&{\tt SCAN} ``11 {\tt SCAN}$a$ {\tt PUSH}$a$''\cr
\noalign{\bigskip\bigskip}
&&&&\hfill{\tt PUSH} $a$ {\tt WRITE} $a$\cr
\noalign{\bigskip\bigskip}
&&{\tt SCAN} ``1''&&{\tt SCAN} ``12 {\tt NOOP NOOP}''\cr
\Rightarrow&0&&1&&2&etc.\cr
\noalign{\bigskip\bigskip}
&&&&{\tt SCAN} ``11 {\tt SCAN} $b$ {\tt PUSH} $b$''\cr
\noalign{\bigskip\bigskip}
&&&&\hfill {\tt PUSH} $b$ {\tt WRITE} $b$\cr
}}$$

\bigskip
\noindent
The domain of this machine, call it $\pi↓{\rm input}$, is still the set
of computations of~$\pi$, but it has output, and its range is the set
of strings $\pi$~can accept, dom~$\pi$.

So $\pi↓{\rm input}$ is deterministic, and ran $\pi↓{\rm input}={\rm dom}\;\pi$.
A~similar modification gives $\pi↓{\rm output}$, which writes exactly
what $\pi$ writes, so ran $\pi↓{\rm output}={\rm ran}\;\pi$. Finally,
we can modify $\pi↓{\rm chk}$ to have two inputs and an output. From
the first input, it reads a computation of~$\pi$. From the second, it
reads the same string $\pi$ reads. On the output, it writes the same
string $\pi$ writes. So if $\pi$: $x\mapsto y$, there is a computation
$w$ for~$\pi$ that accepts~$x$ and writes~$y$, and $\pi↓{\rm io}$ reads
$\langle w,x\rangle$ and writes~$y$.

Let's say that a deterministic program computes the transfer relation
$\tau =\{\langle x↓i,y↓i\rangle\}$ {\sl with help\/} if for each
$\langle x↓i,y↓i\rangle\in\tau$ there is a string $w↓i$, and the program maps
$\langle w↓i,x↓i\rangle\mapsto y↓i$.

More precisely,
$$x\tau y≡\exists w \mid\langle w,x\rangle\mapsto y\,.$$
Then the construction of the checking machine shows that for every
nondeterministic machine~$\pi$, there is a deterministic machine $\pi↓{\rm io}$
that, with help, computes the transfer relation of~$\pi$. For the case
that $\pi$ writes nothing, so its transfer relation is $L\times\Lambda$,
and it accepts language~$L$, $\pi↓{\rm input}$ generates~$L$
and $\pi↓{\rm io}$ accepts~$L$ with help.

Pleasantly, these relations among programs go both ways. If program~$\mu$
computes a transfer relation with help, there is a nondeterministic
program to compute that transfer function (without help).
After standardizing~$\mu$ so that operations on input$↓1$ always consist
of a series of scans and a final {\tt EOF}, simply omit input$↓1$ to get~$\mu↓{nd}$.
Every computation of~$\mu$, after omitting mention of input$↓1$, is still
a computation of~$\mu↓{nd}$. Every computation of $\mu↓{nd}$ can be
restored to be a computation of~$\mu$; the restored operations are always
a series of scans followed by one {\tt EOF}, and there is always an initial
state of input$↓1$ for which those operations lead to a final state.

In the same way, if a language $L$ is generated by a deterministic (or even
a nondeterministic) machine, there is a nondeterministic machine that accepts~it.
We conclude:
For a relation~$\tau$, and machine~$X$, $\tau$~is the transfer relation
of a nondeterministic program for~$X$ if and only if $\tau$ is computed with
help by a deterministic program for~$X$. For a language~$L$ and machine~$X$,
these are equivalent: $L$~is accepted by a nondeterministic program for~$X$,
$L$~is generated by a nondeterministic program for~$X$, $L$~is generated
by a deterministic program for~$X$. Warning: $L$~may not be accepted by
any deterministic program for~$X$; that depends on~$X$.

\bye